home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / reuse.lha / reuse / c / Memory.c < prev    next >
C/C++ Source or Header  |  1992-08-18  |  7KB  |  230 lines
  1. /* $Id: Memory.c,v 1.13 1992/06/24 12:23:15 grosch rel $ */
  2.  
  3. /* $Log: Memory.c,v $
  4.  * Revision 1.13  1992/06/24  12:23:15  grosch
  5.  * changed cNoMoreSpace from -1 to 0
  6.  *
  7.  * Revision 1.12  1992/05/05  13:19:05  grosch
  8.  * added rcsid
  9.  *
  10.  * Revision 1.11  1992/01/31  16:31:44  grosch
  11.  * adaption to ANSI C
  12.  *
  13.  * Revision 1.10  1992/01/30  13:16:06  grosch
  14.  * redesign of interface to operating system
  15.  *
  16.  * Revision 1.9  1992/01/14  15:24:35  grosch
  17.  * introduced automatic initialization
  18.  *
  19.  * Revision 1.8  1991/11/21  14:28:16  grosch
  20.  * new version of RCS on SPARC
  21.  *
  22.  * Revision 1.7  91/01/21  12:13:22  grosch
  23.  * some performance improvements
  24.  * 
  25.  * Revision 1.6  90/12/14  15:55:52  grosch
  26.  * introduced variable MemoryUsed
  27.  * 
  28.  * Revision 1.5  90/09/14  11:20:46  grosch
  29.  * removed superfluous declarations for automatic alignment
  30.  * 
  31.  * Revision 1.4  90/09/04  17:32:10  grosch
  32.  * automatic determination of alignment
  33.  * 
  34.  * Revision 1.3  90/07/04  14:33:58  grosch
  35.  * introduced conditional include
  36.  * 
  37.  * Revision 1.2  89/12/08  20:16:43  grosch
  38.  * added alignment for MIPS processor
  39.  * 
  40.  * Revision 1.1  89/06/06  10:28:54  grosch
  41.  * fixed lint problem at call of Free
  42.  * 
  43.  * Revision 1.0  88/10/04  11:44:41  grosch
  44.  * Initial revision
  45.  * 
  46.  */
  47.  
  48. /* Ich, Doktor Josef Grosch, Informatiker, Sept. 1987 */
  49.  
  50. static char rcsid [] = "$Id: Memory.c,v 1.13 1992/06/24 12:23:15 grosch rel $";
  51.  
  52. # include "ratc.h"
  53. # include "Memory.h"
  54. # include "System.h"
  55. # include "General.h"
  56. # include <stdio.h>
  57.  
  58. # define MinSizeSmallBlock    4
  59. # define MaxSizeSmallBlock    62    /* 64 - 2    */
  60. # define MinSizeLargeBlockLog    6    /* Log2 64    */
  61. # define MaxSizeLargeBlockLog    24    /* Log2 2**24    */
  62. # define PoolSize        10240L
  63. # define NIL            (tBlockPtr) NULL
  64.  
  65. unsigned long MemoryUsed = 0;
  66.  
  67. struct tBlock {
  68.    struct tBlock *    Successor;
  69.    unsigned long    Size;
  70. };
  71. typedef struct tBlock *    tBlockPtr;
  72. typedef cardinal    tSmallBlockRange;
  73. typedef cardinal    tLargeBlockRange;
  74.  
  75. static    tBlockPtr    SmallChain [MaxSizeSmallBlock    + 1] = { 0,
  76.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  77.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  78.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  79.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  80.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  81.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  82.    NIL, NIL,
  83. };
  84. static    tBlockPtr    LargeChain [MaxSizeLargeBlockLog + 1] = { 0,
  85.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  86.    NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL, NIL,
  87.    NIL, NIL, NIL, NIL,
  88. };
  89. static    char *        PoolFreePtr = 0;
  90. static    char *        PoolEndPtr  = 0;
  91.  
  92. char * Alloc (ByteCount)
  93.    register unsigned long ByteCount;
  94.  
  95. /* Returns a pointer to dynamically allocated    */
  96. /* space of size 'ByteCount' bytes.        */
  97.  
  98. {
  99.    ByteCount = (ByteCount + yyMaxAlign - 1) & yyAlignMasks [yyMaxAlign];
  100.  
  101.    if (ByteCount <= MaxSizeSmallBlock) {    /* handle small block */
  102.       if (ByteCount < MinSizeSmallBlock) ByteCount = MinSizeSmallBlock;
  103.       if (SmallChain [ByteCount] != NIL) {    /* obtain block from freelist */
  104.      register tBlockPtr CurrentBlock = SmallChain [ByteCount];
  105.      SmallChain [ByteCount] = CurrentBlock->Successor;
  106.      return (char *) CurrentBlock;
  107.       } else {                    /* obtain block from storage pool */
  108.      register unsigned long FreeBytes;
  109.      register char *    OldFreePtr;
  110.                         /* release old pool */
  111.      if ((FreeBytes = PoolEndPtr - PoolFreePtr) < ByteCount) {
  112.         if (FreeBytes >= MinSizeSmallBlock) Free (FreeBytes, PoolFreePtr);
  113.         PoolFreePtr = Alloc (PoolSize);    /* allocate new pool */
  114.         PoolEndPtr  = PoolFreePtr + PoolSize;
  115.      }
  116.      OldFreePtr = PoolFreePtr;
  117.      PoolFreePtr += ByteCount;
  118.      return OldFreePtr;
  119.       }
  120.    } else {                    /* handle large block */
  121.  
  122.       /* 1. search in LargeChain [Log2 (ByteCount)] using BEST FIT */
  123.  
  124.       register cardinal        ChainNumber    = Log2 (ByteCount);
  125.       register tBlockPtr    CurrentBlock    = LargeChain [ChainNumber];
  126.       register tBlockPtr    PreviousBlock    = (tBlockPtr) & (LargeChain [ChainNumber]);
  127.       register tBlockPtr    BestBlock    = NIL;
  128.       register unsigned long    BestBlockSize    = 1000000000;
  129.       register tBlockPtr    PredecessorBlock;
  130.       register tLargeBlockRange    j        ;
  131.       register unsigned long    CurrentBlockSize;
  132.  
  133.       while (CurrentBlock) {
  134.      CurrentBlockSize = CurrentBlock->Size;
  135.      if (CurrentBlockSize >= ByteCount) {
  136.         if (CurrentBlockSize == ByteCount) { /* exact match */
  137.            PreviousBlock->Successor = CurrentBlock->Successor;
  138.            return (char *) CurrentBlock;
  139.         }
  140.         if (CurrentBlockSize < BestBlockSize) { /* improve approximation */
  141.            BestBlock    = CurrentBlock;
  142.            BestBlockSize    = CurrentBlockSize;
  143.            PredecessorBlock    = PreviousBlock;
  144.         }
  145.      }
  146.      PreviousBlock    = CurrentBlock;
  147.      CurrentBlock    = CurrentBlock->Successor;
  148.       }
  149.  
  150.       if (BestBlock) {
  151.      PredecessorBlock->Successor = BestBlock->Successor;
  152.      if (BestBlockSize - ByteCount >= MinSizeSmallBlock) {
  153.         Free (BestBlockSize - ByteCount, (char *) BestBlock + ByteCount);
  154.      }
  155.      return (char *) BestBlock;
  156.       }
  157.  
  158.       /* 2. search in LargeChain [j], j > Log2 (ByteCount), using FIRST FIT */
  159.  
  160.       for (j = ChainNumber+1; j <= MaxSizeLargeBlockLog; j ++) {
  161.      CurrentBlock = LargeChain [j];
  162.      if (CurrentBlock != NIL) {
  163.         LargeChain [j] = CurrentBlock->Successor;
  164.         if (CurrentBlock->Size - ByteCount >= MinSizeSmallBlock) {
  165.            Free (CurrentBlock->Size - ByteCount, (char *) CurrentBlock + ByteCount);
  166.         }
  167.         return (char *) CurrentBlock;
  168.      }
  169.       }
  170.  
  171.       if (ByteCount < PoolSize) {        /* 3. obtain block from storage pool */
  172.      register unsigned long FreeBytes;
  173.                         /* release old pool */
  174.      if ((FreeBytes = PoolEndPtr - PoolFreePtr) < ByteCount) {
  175.         if (FreeBytes >= MinSizeSmallBlock) Free (FreeBytes, PoolFreePtr);
  176.         PoolFreePtr = Alloc (PoolSize);    /* allocate new pool */
  177.         PoolEndPtr  = PoolFreePtr + PoolSize;
  178.      }
  179.      PoolFreePtr += ByteCount;
  180.      return PoolFreePtr - ByteCount;
  181.       } else {                    /* 4. allocate individual block */
  182.      CurrentBlock = (tBlockPtr) SysAlloc ((long) ByteCount);
  183.      MemoryUsed += ByteCount;
  184.      return (char *) CurrentBlock;
  185.       }
  186.    }
  187. }
  188.  
  189. void Free (ByteCount, a)
  190.    unsigned long    ByteCount;
  191.    char *        a;
  192.  
  193. /* The dynamically allocated space starting at    */
  194. /* address 'a' of size 'ByteCount' bytes is    */
  195. /* released.                    */
  196.  
  197. {
  198.    register tBlockPtr        BlockPtr;
  199.    register tLargeBlockRange    ChainNumber;
  200.  
  201.    ByteCount = (ByteCount + yyMaxAlign - 1) & yyAlignMasks [yyMaxAlign];
  202.  
  203.    BlockPtr = (tBlockPtr) a;
  204.    if (ByteCount <= MaxSizeSmallBlock) {
  205.       if (ByteCount < MinSizeSmallBlock) ByteCount = MinSizeSmallBlock;
  206.       BlockPtr->Successor    = SmallChain [ByteCount];
  207.       SmallChain [ByteCount]    = BlockPtr;
  208.    } else {
  209.       ChainNumber        = Log2 (ByteCount);
  210.       BlockPtr->Successor    = LargeChain [ChainNumber];
  211.       BlockPtr->Size        = ByteCount;
  212.       LargeChain [ChainNumber]    = BlockPtr;
  213.    }
  214. }
  215.  
  216. void InitMemory ()
  217. {
  218.    register int i;
  219.  
  220.    for (i = MinSizeSmallBlock; i <= MaxSizeSmallBlock; i += 2) {
  221.       SmallChain [i] = NIL;
  222.    }
  223.    for (i = MinSizeLargeBlockLog; i <= MaxSizeLargeBlockLog; i ++) {
  224.       LargeChain [i] = NIL;
  225.    }
  226.    MemoryUsed    = 0;
  227.    PoolFreePtr    = 0;
  228.    PoolEndPtr    = 0;
  229. }
  230.